{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Convex Polygon"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isConvex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #凸多边形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定 <strong>X-Y</strong> 平面上的一组点&nbsp;<code>points</code>&nbsp;，其中&nbsp;<code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 。这些点按顺序连成一个多边形。</p>\n",
    "\n",
    "<p>如果该多边形为&nbsp;<strong>凸</strong>&nbsp;多边形<a href=\"https://baike.baidu.com/item/凸多边形/\">（凸多边形的定义）</a>则返回 <code>true</code> ，否则返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以假设由给定点构成的多边形总是一个 简单的多边形<a href=\"https://baike.baidu.com/item/%E7%AE%80%E5%8D%95%E5%A4%9A%E8%BE%B9%E5%BD%A2\">（简单多边形的定义）</a>。换句话说，我们要保证每个顶点处恰好是两条边的汇合点，并且这些边&nbsp;<strong>互不相交&nbsp;</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/09/covpoly1-plane.jpg\" style=\"height: 294px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> points = [[0,0],[0,5],[5,5],[5,0]]\n",
    "<strong>输出:</strong> true</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/09/covpoly2-plane.jpg\" style=\"height: 303px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> points = [[0,0],[0,10],[10,10],[10,0],[5,5]]\n",
    "<strong>输出:</strong> false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= points.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>所有点都 <strong>不同</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [convex-polygon](https://leetcode.cn/problems/convex-polygon/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [convex-polygon](https://leetcode.cn/problems/convex-polygon/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[0,5],[5,5],[5,0]]', '[[0,0],[0,10],[10,10],[10,0],[5,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isConvex(self, points: List[List[int]]) -> bool:\n",
    "        n = len(points)\n",
    "        pre = 0\n",
    "        for i in range(n):\n",
    "            x1 = points[(i + 1) % n][0] - points[i][0]\n",
    "            x2 = points[(i + 2) % n][0] - points[i][0]\n",
    "            y1 = points[(i + 1) % n][1] - points[i][1]\n",
    "            y2 = points[(i + 2) % n][1] - points[i][1]\n",
    "            cur = x1*y2 - x2*y1\n",
    "            if cur !=0:\n",
    "                if cur * pre <0:\n",
    "                    return False\n",
    "                else:\n",
    "                    pre=cur\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isConvex(self, points: List[List[int]]) -> bool:\n",
    "        judge=\"s\"\n",
    "        for i in range(len(points)):\n",
    "            vector1=[points[i%len(points)][0]-points[(i+1)%len(points)][0],points[i%len(points)][1]-points[(i+1)%len(points)][1]]\n",
    "            vector2=[points[(i+2)%len(points)][0]-points[(i+1)%len(points)][0],points[(i+2)%len(points)][1]-points[(i+1)%len(points)][1]]\n",
    "            temp=vector1[0]*vector2[1]-vector1[1]*vector2[0]\n",
    "            if judge==\"s\":\n",
    "                if temp==0:\n",
    "                    continue\n",
    "                judge=vector1[0]*vector2[1]-vector1[1]*vector2[0]\n",
    "            else:\n",
    "                if (temp>0 and judge<0) or (temp<0 and judge>0):\n",
    "                    return False\n",
    "        if judge!='s':\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isConvex(self, points: List[List[int]]) -> bool:\n",
    "        n = len(points)\n",
    "        points.append(points[0])\n",
    "        points.append(points[1])\n",
    "\n",
    "        pre = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i+1][0] - points[i][0], points[i+1][1] - points[i][1]\n",
    "            x2, y2 = points[i+2][0] - points[i+1][0], points[i+2][1] - points[i+1][1]\n",
    "            tmp = x1 * y2 - x2 * y1\n",
    "            if tmp != 0:\n",
    "                if pre * tmp < 0:\n",
    "                    return False\n",
    "                pre = tmp\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isConvex(self, points: List[List[int]]) -> bool:\n",
    "        # 相邻两个向量的定向必须一致\n",
    "        n=len(points)\n",
    "        vcts=[]\n",
    "        for i in range(n):\n",
    "            vcts.append([points[(i+1)%n][0]-points[i][0],points[(i+1)%n][1]-points[i][1]])\n",
    "        positive=negative=False\n",
    "        for i in range(n):\n",
    "            dot=vcts[i][0]*vcts[(i+1)%n][1]-vcts[i][1]*vcts[(i+1)%n][0]\n",
    "            if dot>0:\n",
    "                positive=True\n",
    "            elif dot<0:\n",
    "                negative=True\n",
    "            if positive and negative:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isConvex(self, points: List[List[int]]) -> bool:\n",
    "        points.append(points[0])\n",
    "        points.append(points[1])\n",
    "\n",
    "        n = len(points)\n",
    "        now = 0\n",
    "        for i in range(0, n - 2):\n",
    "            p1 = points[i]\n",
    "            p2 = points[i + 1]\n",
    "            p3 = points[i + 2]\n",
    "\n",
    "            x1 = p2[0] - p1[0]\n",
    "            y1 = p2[1] - p1[1]\n",
    "\n",
    "            x2 = p3[0] - p2[0]\n",
    "            y2 = p3[1] - p2[1]\n",
    "\n",
    "            temp = x1*y2 - x2*y1\n",
    "            if temp != 0:\n",
    "                if temp * now < 0:\n",
    "                    return False\n",
    "                elif now == 0:\n",
    "                    now = temp\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isConvex(self, points: List[List[int]]) -> bool:\n",
    "\n",
    "        n = len(points)\n",
    "        pre = 0\n",
    "        for i in range(n):\n",
    "            x1 = points[(i + 1) % n][0] - points[i][0]\n",
    "            x2 = points[(i + 2) % n][0] - points[i][0]\n",
    "            y1 = points[(i + 1) % n][1] - points[i][1]\n",
    "            y2 = points[(i + 2) % n][1] - points[i][1]\n",
    "            cur = x1*y2 - x2*y1\n",
    "            if cur !=0:\n",
    "                if cur * pre <0:\n",
    "                    return False\n",
    "                else:\n",
    "                    pre=cur\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isConvex(self, points: List[List[int]]) -> bool:\n",
    "\n",
    "        # 第一步：找到最小最左的点作为凸包扫描的起点\n",
    "        start = [float('inf'), float('inf')]\n",
    "        for x, y in points:\n",
    "            if y < start[1] or (y == start[1] and x < start[0]):\n",
    "                start = [x, y]\n",
    "\n",
    "        # 第二步：按照所有点到起点的极角与距离排序\n",
    "        def angle(node):\n",
    "            x, y = node\n",
    "            # 极角取值范围为[0, 180)\n",
    "            cur = math.atan2(y - start[1], x - start[0]) * 180 / math.pi\n",
    "            # 极角同样的情况下横坐标距离即可表示欧式距离\n",
    "            return [cur, abs(x - start[0])]\n",
    "        points.sort(key=lambda x: angle(x))\n",
    "\n",
    "\n",
    "        # 第三步：依次检查相邻节点组成的向量对方向关系，凸包要求逆时针或者共线\n",
    "        def check(node1, node2, node3):\n",
    "            x2, y2 = node2[0] - node1[0], node2[1] - node1[1]\n",
    "            x3, y3 = node3[0] - node1[0], node3[1] - node1[1]\n",
    "            # 大于0逆时针，等于0共线，小于0顺时针\n",
    "            return x2 * y3 - y2 * x3 >= 0\n",
    "\n",
    "        n = len(points)\n",
    "        for j in range(2, n):\n",
    "            if not check(points[j - 2], points[j - 1], points[j]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isConvex(self, points: List[List[int]]) -> bool:\n",
    "        n = len(points)\n",
    "\n",
    "        pre = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x1 = points[(i+1) % n][0] - points[i][0];\n",
    "            y1 = points[(i+1) % n][1] - points[i][1];\n",
    "\n",
    "            x2 = points[(i+2) % n][0] - points[(i+1) % n][0];\n",
    "            y2 = points[(i+2) % n][1] - points[(i+1) % n][1];\n",
    "\n",
    "            tmp = x1 * y2 - x2 * y1\n",
    "\n",
    "            if tmp != 0:\n",
    "                if pre * tmp < 0:   ##与上一次的法向量方向相反\n",
    "                    return False\n",
    "                \n",
    "                pre = tmp\n",
    "        \n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
